package org.example;

import java.util.ArrayDeque;
import java.util.Deque;

public class Test2 {
    public int[] dailyTemperatures(int[] temperatures) {
        //使用单调栈来存放已经遍历过的元素，并且因为求的是下一个更高温度出现的时候，所以是单调递增栈
        //单调栈中存放的是元素的下标
        Deque<Integer> deque = new ArrayDeque<>();
        deque.add(0);
        int n = temperatures.length;
        int[] ret = new int[n];
        for (int i = 1; i < n; i++) {
            if (temperatures[i] > temperatures[deque.peekFirst()]) {
                while (!deque.isEmpty() && temperatures[deque.peekFirst()] < temperatures[i]) {
                    int tmp = deque.removeFirst();
                    ret[tmp] = i-tmp;
                }
            }
            deque.addFirst(i);
        }
        return ret;
    }

    public static void main(String[] args) {
        Test2 test2 = new Test2();
        int[] arr = {73,74,75,71,69,72,76,73};
        test2.dailyTemperatures(arr);
        System.out.println(666);
    }
}
